package ai.minimax;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;

import search.Search;
import hexgame.GameLogic;
import hexgame.GameState;
import hexgame.HexMove;
import hexgame.HexPlayer;
import hexgame.Player;

public class MiniMaxAI extends Player {

	boolean isFirst;
	boolean bridging;
	GameState state;
	int maxDepth;
	int numCalls;
	int calculatedAlpha;
	
	int numThreads;
	Thread[] threads;
	
	
	public MiniMaxAI(GameState state, int depth, boolean bridging) {
		isFirst = true;
		this.state = state;
		this.maxDepth = depth;
		this.bridging = bridging;
		this.numThreads = Runtime.getRuntime().availableProcessors();
		
		threads = new Thread[numThreads];
	}
	
	@Override
	public boolean isConnected() {
		return true;
	}

	@Override
	public HexMove getMove() {
		return decideMove();
	}
	
	private HexMove decideMove() {
		HexMove move = miniMaxStart(this.maxDepth, state);
		
		if(bridging) {
			// We must have found a move we definitely must take to try and prevent losing
			if(calculatedAlpha < Integer.MAX_VALUE + state.getBoardSize()) {
				return move;
			}
			
			// Defend our zero connected moves.
			HexMove defend = defendLinks();
			
			if(defend != null) {
				return defend;
			}
			
			// If we still haven't played any moves yet, the first one we calculated can be our next move
			return move;
		}
		
		return move;
	}
	
	private HexMove defendLinks() {
		
		// To find all the links we need to defend, we get the shortest path from edge to edge.
		HexMove[] moves = leastTurnsEdgeToEdge(state, true);
		
		if(moves == null) {
			// It seems we have lost
		}
		
		// Then for every move
		for(int i=0; i<moves.length-1; i++) {
			HexMove move = moves[i];
			
			// If we haven't played this move yet
			if(move.getPlayer() == HexPlayer.NONE) {
				continue;
			}
			
			HexMove nextMove = null;
			
			for(int j=i; j<moves.length; j++) {
				if(moves[j].getPlayer() == HexPlayer.RED_LOCAL) {
					nextMove = moves[j];
					i = j;
				}
			}
			if(nextMove == null) {
				return null;
			}
			
			// First we check if we have played 
			
			// We see if it's no longer an option for being zero connecting
			if(!GameLogic.getZeroConnectingMoves(move, state).contains(nextMove)) {
				// Then we get link positions for the move
				HexMove[] links = GameLogic.getLinkPositions(move, nextMove);
				
				// Then if none of them are RED_LOCAL and one of them is BLUE_REMOTE, we play the other move.
				if(links[0].getPlayer() != HexPlayer.RED_LOCAL && links[1].getPlayer() != HexPlayer.RED_LOCAL) {
					if(links[0].getPlayer() == HexPlayer.BLUE_REMOTE) {
						return links[1];
					}
					if(links[1].getPlayer() == HexPlayer.BLUE_REMOTE) {
						return links[0];
					}
				}
			}
		}
		return null;
	}
	
	private HexMove miniMaxStart(int depth, GameState state) {
		
		numCalls = 0;
		long startTime = System.currentTimeMillis();
		
		
		int alpha = Integer.MAX_VALUE;
		HexMove chosen = null;
		
		ArrayList<HashSet<HexMove>> moves = new ArrayList<HashSet<HexMove>>();
		
		for(int i = 0; i<numThreads; i++) {
			moves.add(i, new HashSet<HexMove>());
		}
		int processor = 0;
		
		for(int x=0; x<state.getBoardSize(); x++) {
			for(int y=0; y<state.getBoardSize(); y++) {
				if(processor >= this.numThreads) {
					processor = 0;
				}
				
				HexPlayer hexstate = state.getHexState(x, y);
				
				// We decide to search tiles which either 1;
					// 1. surround our tiles
					// 2. surround their tiles
					// 3. are on either boundary of our winning target
				 
				if(isFirst) {
					if(hexstate == HexPlayer.NONE) {
						moves.get(processor).add(new HexMove(x, y, HexPlayer.NONE));
					}
				}
				else {
					if(hexstate != HexPlayer.NONE) {
						moves.get(processor).addAll(GameLogic.getValidZeroConnectedHexagons(new HexMove(x, y, HexPlayer.RED_LOCAL), state));
					}
				}
				
			}
		}
		MiniMaxThread[] runnables = new MiniMaxThread[numThreads];
		isFirst = false;
		for(int i = 0; i<numThreads; i++) {
			
			HexMove[] moveArray = moves.get(i).toArray(new HexMove[moves.get(i).size()]);
			runnables[i] = new MiniMaxThread(state, moveArray, depth, this.bridging);
			threads[i] = new Thread(runnables[i]);
			threads[i].start();
		}
		
		for(int i = 0; i<numThreads; i++) {
			try {
				threads[i].join();
				
				if(alpha > runnables[i].getScore()) {
					chosen = runnables[i].getMove();
					alpha = runnables[i].getScore();
				}
			}
			catch (InterruptedException e) {
				// Discard results
				continue;
			}
		}
		
		long totalTime = System.currentTimeMillis() - startTime;
		System.out.println("AI: Chosen " + chosen.getX() + " " + chosen.getY() + " with alpha: " + alpha + ". Took " + totalTime + "ms to discover path");
		
		return new HexMove(chosen.getX(), chosen.getY(), HexPlayer.RED_LOCAL);
	}
	
	/**
	 * Minimax AI technique. However due to the fact our ranking method is a lowest-best method, the minimax is performed backwards
	 * @param node - The first move to search from in this call of the method
	 * @param depth - The depth to search to. Is decremented with every recursive call until it is zero
	 * @param oldState - The current GameState. Is untouched by this function
	 * @param maximise - Should we choose what is best for us, or worst for us?
	 * @return the number of moves left until we win with this move
	 */
	public static int miniMax(HexMove node, int depth, GameState oldState, boolean maximise, int maxDepth, boolean bridging, int alpha, int beta) {
		// Create a new GameState to test the potential moves on
		
		GameState newState = new GameState(oldState);
		GameLogic.makeMove(newState, node);
		HexPlayer winState = GameLogic.playerWon(newState);
		if(winState != HexPlayer.NONE) {
			if(winState == HexPlayer.RED_LOCAL) {
				return Integer.MIN_VALUE + maxDepth - depth;
			}
			else {
				return Integer.MAX_VALUE - maxDepth + depth;
			}
		}
		
		HexPlayer player = HexPlayer.RED_LOCAL;
		
		if(!maximise) {
			player = HexPlayer.BLUE_REMOTE;
		}
		
		if(depth <= 0) {
			Integer moves = null;
			if(bridging) {
				moves = minimumMovesUntilTargetBridge(newState, true);
			}
			else {
				moves = minimumMovesUntilTarget(newState, true);
			}
			
			if(moves == null) {
				return alpha;
			}
			else {
				return moves;
			}
		}
		
		// Using a set should reduce the number we check.
		// Unsure if the comparison is more expensive than actually checking it though
		Collection<HexMove> moves = new HashSet<HexMove>();
		for(int x=0; x<newState.getBoardSize(); x++) {
			for(int y=0; y<newState.getBoardSize(); y++) {
				HexPlayer hexstate = newState.getHexState(x, y);
				
				if(hexstate != HexPlayer.NONE) {
					// Include bridge moves soon?
					if(bridging) {
						moves.addAll(GameLogic.getValidZeroConnectedHexagons(new HexMove(x, y, player), newState));
					}
					else {
						moves.addAll(GameLogic.getValidConnectingMoves(new HexMove(x, y, player), newState));
					}
					
				}
			}
		}
		if(maximise) {
			for(HexMove move : moves) {
				int score = miniMax(new HexMove(move.getX(), move.getY(), player), depth - 1, newState, !maximise, maxDepth, bridging, alpha, beta);
				
				beta = Math.min(beta, score);
				
				if(beta <= alpha) {
					break;
				}
			}
			return beta;
		}
		else {
			for(HexMove move : moves) {
				int score = miniMax(new HexMove(move.getX(), move.getY(), player), depth - 1, newState, !maximise, maxDepth, bridging, alpha, beta);
				
				alpha = Math.max(alpha, score);
				
				if(beta <= alpha) {
					break;
				}
			}
			return alpha;
		}
		
	}
	
	/**
	 * Gets the minimum number of moves left to perform until the specified target is reached
	 * @param state - GameState to perform the check on
	 * @param rightEdge - Should we aim towards the rightEdge (or the bottom edge?)
	 * @return the number of moves, or Integer.MAX_VALUE if it's not possible
	 */
	public static int minimumMovesUntilTarget(GameState state, boolean rightEdge) {
		HexMove[] moves = leastTurnsEdgeToEdge(state, rightEdge);
		if(moves == null) { 
			return Integer.MAX_VALUE;
		}
		return moves.length;
	}
	
	/**
	 * Gets the minimum number of moves left to perform until the specified target is reached
	 * @param state - GameState to perform the check on
	 * @param rightEdge - Should we aim towards the rightEdge (or the bottom edge?)
	 * @return the number of moves, or Integer.MAX_VALUE if it's not possible
	 */
	public static int minimumMovesUntilTargetBridge(GameState state, boolean rightEdge) {
		HexMove[] moves = leastTurnsEdgeToEdge(state, rightEdge);
		if(moves == null) { 
			return Integer.MAX_VALUE;
		}
		return moves.length;
	}
	
	private static HexMove[] leastTurnsEdgeToEdge(GameState state, boolean rightEdge) {
		int min = Integer.MAX_VALUE;
		HexMove[] shortMoves = null;
		HexPlayer player;
		
		if(rightEdge) {
			player = HexPlayer.RED_LOCAL;
		} else {
			player = HexPlayer.BLUE_REMOTE;
		}
		
		for(int i=0; i<state.getBoardSize(); i++) {
			HexMove hexState;
			
			if(rightEdge) {
				hexState = new HexMove(0, i, state.getHexState(0, i));
			}
			else {
				hexState = new HexMove(i, 0, state.getHexState(i, 0));
			}
			
			if(hexState.getPlayer() == player) {
				
				HexMove[] moves = Search.leastTurnsToEdge(hexState, state, rightEdge);
				
				if(moves == null) {
					continue;
				}
				if(min > moves.length) {
					
					min = Math.min(min, moves.length);
					shortMoves = moves;
				}
			}
			
			// We also test going from the empty tile to the other side, to see if it'd be faster
			else {
				if(state.getHexState(0, i) == HexPlayer.NONE) {
					HexMove[] moves = Search.leastTurnsToEdge(hexState, state, rightEdge);
					
					if(moves == null) {
						continue;
					}
					if(min > moves.length) {
					
						min = Math.min(min, moves.length);
						shortMoves = moves;
					}
				}
			}
		}
		return shortMoves;
	}

	@Override
	public void showMove(HexMove move) {
		// TODO Auto-generated method stub
		
	}

	@Override
	public void gameOver(boolean didWin) {
		// TODO Auto-generated method stub

	}

	@Override
	public void sendErrorMessage(String message) {
		// TODO Auto-generated method stub

	}

}
